package 算法复习课.手动造轮子.tree;

/**
 * 二叉树
 *
 * @author linhao
 * @date created in 5:32 下午 2020/10/23
 */
public class BinaryTree {

    private TreeNode root;

    private class TreeNode {
        int data;
        TreeNode right;
        TreeNode left;

        public TreeNode(int value) {
            this.data = value;
            right = null;
            left = null;
        }

        public TreeNode() {
        }
    }

    private void readNode(TreeNode treeNode){
        System.out.println(treeNode.data);
    }

    /**
     * 选择不同的方式进行遍历
     *
     * @param type 1前序遍历 2中序遍历 3后序遍历
     */
    public void iteratorFromRoot(int type){
        if(type==1){
            iteratorFirstOrder(root);
        } else if(type==2){
            iteratorMidOrder(root);
        } else if(type==3){
            iteratorLeftOrder(root);
        }
    }

    public void iteratorFirstOrder(TreeNode node){
        if(node==null){
            return;
        }
        readNode(node);
        iteratorFirstOrder(node.left);
        iteratorFirstOrder(node.right);
    }

    public void iteratorMidOrder(TreeNode node){
        if(node==null){
            return;
        }
        iteratorMidOrder(node.left);
        readNode(node);
        iteratorMidOrder(node.right);
    }

    public void iteratorLeftOrder(TreeNode node){
        if(node==null){
            return;
        }
        iteratorLeftOrder(node.left);
        iteratorLeftOrder(node.right);
        readNode(node);
    }

    public void insert(int value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
        } else {
            if (value > root.data) {
                TreeNode temp = root;
                while (true) {
                    if (value > temp.data) {
                        if (temp.right == null) {
                            temp.right = newNode;
                            break;
                        }
                        temp = temp.right;
                    } else if (value < temp.data) {
                        if(temp.left == null){
                            temp.left = newNode;
                            break;
                        }
                        temp = temp.left;
                    } else {
                        throw new RuntimeException("has same node");
                    }
                }
            }
        }
    }


    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        binaryTree.insert(1);
        binaryTree.insert(2);
        binaryTree.insert(3);
        binaryTree.insert(4);
        binaryTree.iteratorFromRoot(1);
        binaryTree.iteratorFromRoot(2);
        binaryTree.iteratorFromRoot(3);
    }


}
